%! Author = chouheiwa
%! Date = 2022/10/21

% Preamble
\documentclass[UTF8]{article} %article 文档
\usepackage{ctex}  %使用宏包(为了能够显示汉字)
\usepackage{hyperref}
\usepackage{graphicx}
\usepackage{geometry}
\geometry{a4paper,scale=0.8}
\usepackage{listings}
\usepackage{color}
\definecolor{dkgreen}{rgb}{0,0.6,0}
\definecolor{gray}{rgb}{0.5,0.5,0.5}
\definecolor{mauve}{rgb}{0.58,0,0.82}
\lstset{frame=tb,
    language=Python,
    aboveskip=3mm,
    belowskip=3mm,
    showstringspaces=false,
    columns=flexible,
    basicstyle={\small\ttfamily},
    numbers=left,%设置行号位置none不显示行号
%numberstyle=\tiny\courier, %设置行号大小
    numberstyle=\tiny\color{gray},
    keywordstyle=\color{blue},
    commentstyle=\color{dkgreen},
    stringstyle=\color{mauve},
    breaklines=true,
    breakatwhitespace=true,
    escapeinside=``,%逃逸字符(1左面的键)，用于显示中文例如在代码中`中文...`
    tabsize=4,
    extendedchars=false %解决代码跨页时，章节标题，页眉等汉字不显示的问题
}

% Packages
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amssymb}

% Document
\title{机器学习课程作业1}
\author{chouheiwa}
\date{2022/10/21}
\linespread{1.5}
\begin{document}
    \maketitle
    \tableofcontents


    \section{问题一}
    这里无法避免使用到矩阵的算法，以及绘图的算法，所以代码中会额外需要使用到numpy（用以进行数学运算）和matplotlib（用以生成和绘制相关散点图及分界线图）这两个库。

    \subsection{第一小问}
    这里已知要生成N = 1000个二维样本的数据集$X_1$和$X_2$。又知晓样本来自于三个不同的正态分布，其分布的均值矢量分别为
    \[
        m_1 = [1, 1]^T\\m_2 = [4, 4]^T\\m_3 = [8, 1]^T
    \]
    协方差为
    \[
        \Sigma_1 = \Sigma_2 = \Sigma_3 = \begin{bmatrix}
                                             2 & 0 \\ 0 & 2
        \end{bmatrix}
    \]

    因此，我们可以先生成三个正态分布的随机数，然后再将其乘以协方差矩阵，最后再加上均值矢量，即可得到三个正态分布的样本。这里我们使用 numpy 的 random.multivariate\_normal 函数来生成对应数据集。

    生成数据集功能使用了名为GenerateData作为根据给定参数自动生成相关数据集的功能的类，其代码于文件\href{run:generate_data.py}{generate\_data.py}中。

    绘制数据图像功能代码于文件\href{run:plot_image.py}{plot\_image.py}中。

    main.py函数中会调用上述部分代码，生成数据集并绘制对应数据集$X_1$、$X_2$的散点图图像。示例结果如下图所示。


    \begin{minipage}[t]{0.5\linewidth}
        \centering
        \includegraphics[width=\linewidth]{../question1/X1_data}
    \end{minipage}%
    \begin{minipage}[t]{0.5\linewidth}
        \centering
        \includegraphics[width=\linewidth]{../question1/X2_data}
    \end{minipage}

    \subsection{第二小问} \label{sec:question1_2}
    代码总体解决方案上因为采用了父类和子类的多态设计，所以在main.py中只需要调用类的方法即可，不需要关心具体的实现细节。因此，这里只需要介绍类的设计思路。

    类文件为\href{run:probability_calculate.py}{probability\_calculate.py}。其中，父类(基类)为 ProbabilityCalculate 其主要负责实现通用判别函数，以及其他相关绘制分类线的方法，父类的存在使得子类只需要继承父类的功能，并实现对应计算$g_k(x)$函数的方法即可作为对应的分类器，而无需关心其他细节。加强了代码的复用性。

    因此这里对接下来的三种分类器均计算出$g_k(x)$的表达式便可以完成对应的分类器的设计。

    \subsubsection{似然率决策规则}\label{subsubsec:likelihood}
    似然率决策规则的基本思想是，对于给定的样本，我们可以通过计算其属于各个类别的概率，然后选择概率最大的类别作为其所属类别。因此，对于给定的样本$x$，其属于类别$m_k$的概率为
    \begin{equation}
        P(m_k|x) = \frac{P(x|m_k)P(m_k)}{P(x)} \label{eq:a}
    \end{equation}

    其中，$P(x|m_k)$为似然率，$P(m_k)$为先验概率，$P(x)$为归一化因子。由于$P(x)$对于所有类别$k$都是相同的，因此我们可以忽略该项，即
    \begin{equation}
        P(m_k|x) \propto P(x|m_k)P(m_k) \label{eq:b}
    \end{equation}

    即可以令
    \begin{equation}
        g_k(x) = P(m_k|x) \label{eq:c}
    \end{equation}
    则我们可以通过计算$g_k(x)$的值，然后选择最大的$g_k(x)$对应的类别$m_k$作为样本$x$的预测类别。

    又因为题目中给定数据集是从属于三个正态分布的$m_1$、$m_2$、$m_3$，所以其属于类别$m_k$的似然率$P(x|m_k)$可以写成:
    \begin{equation}
        P(x|m_k) = \frac{1}{(2\pi)^{\frac{d}{2}}|\Sigma_k|^{\frac{1}{2}}}\exp\left(-\frac{1}{2}(x-m_k)^T\Sigma_k^{-1}(x-m_k)\right) \label{eq:e}
    \end{equation}
    将~\eqref {eq:e}代入~\eqref {eq:b}，则有
    \begin{equation}
        P(m_k|x) \propto \frac{1}{(2\pi)^{\frac{d}{2}}|\Sigma_k|^{\frac{1}{2}}}\exp\left(-\frac{1}{2}(x-m_k)^T\Sigma_k^{-1}(x-m_k)\right)P(m_k) \label{eq:f}
    \end{equation}
    根据题目可知，$m_1$、$m_2$、$m_3$所属正态分布的协方差矩阵均相同，即$|\Sigma_k|$为常数，此时我们可以继续忽略常数项，便可由~\eqref {eq:f}得到
    \begin{equation}
        P(m_k|x) \propto \exp\left(-\frac{1}{2}(x-m_k)^T\Sigma_k^{-1}(x-m_k)\right)P(m_k) \label{eq:g}
    \end{equation}
    此时，我们可以将~\eqref {eq:g}代入~\eqref {eq:c}，则有
    \begin{equation}
        g_k(x) = \exp\left(-\frac{1}{2}(x-m_k)^T\Sigma_k^{-1}(x-m_k)\right)P(m_k) \label{eq:h}
    \end{equation}
    似然率决策规则的分类器设计实验完毕。其代码所属类名为 LikelihoodProbability。

    \subsubsection{贝叶斯风险决策规则}
    贝叶斯风险决策规则的基本思想是，对于给定的样本，我们可以通过计算其属于各个类别的风险，然后选择风险最小的类别作为其所属类别。因此，对于给定的样本$x$，其属于类别$m_i$的风险为
    \begin{equation}
        \Re(\alpha_i|x) = = \sum_{j = 1}^{C} C_{ij} P(m_j|x) \label{eq:i}
    \end{equation}

    其后验概率 $P(m_j|x)$ 表达式为

    \begin{equation}
        P(m_j|x) = \frac{1}{(2\pi)^{\frac{d}{2}} \sqrt{|\Sigma_j|}}e^{-\frac{1}{2}(x-m_j)^T\Sigma_j^{-1}(x-m_j)}\frac{P(m_j)}{p(x)} \label{eq:j}
    \end{equation}

    与似然决策规则相同，其中$\frac{1}{(2\pi)^{\frac{d}{2}} \sqrt{|\Sigma_j|}}$ 与 $\frac{1}{p(x)}$ 为常数，因此可以忽略不计。则~\eqref {eq:j}可写成：

    \begin{equation}
        P(m_j|x) \propto \exp\left( -\frac{1}{2}(x-m_j)^T\Sigma_k^{-1}(x-m_j) \right) P(m_j) \label{eq:k}
    \end{equation}

    贝叶斯风险决策的$g_i(x)$等于~\eqref {eq:i} 同时将~\eqref {eq:k} 代入~\eqref {eq:i}，则有：
    \begin{equation}
        g_i(x) = \sum_{j = 1}^{C} C_{ij} \exp\left( -\frac{1}{2}(x-m_j)^T\Sigma_j^{-1}(x-m_j) \right) P(m_j) \label{eq:l}
    \end{equation}

    与似然率决策规则~\ref{subsubsec:likelihood}不同，贝叶斯风险决策规则需要选取风险最小即$g_i(x)$最小的类别作为其所属类别。

    贝叶斯风险决策规则的分类器设计实验完毕。其代码所属类名为 BayesProbability。

    \subsubsection{最小欧几里得距离分类器}
    其$g_i(x) = \frac{1}{2}(x-m_i)^T(x-m_i)$，去除常数项后为$g_i(x) =  -(x-m_i)^T(x-m_i)$

    最小欧几里得距离分类器的分类器设计实验完毕。其代码所属类名为 EuclidProbability。

    \subsection{第三小问 实验结果分析和分类决策界面与错误}

    分类线绘制方法，可由~\ref{sec:question1_2}中的判决规则得到，我们在最佳选择时，往往采用的是最大(最小)$g_i(x)$的类别作为其所属类别。且题目有且仅有3个类别，因此我们即可得到分类线的定义
    \begin{equation}
        g_i(x) = g_j(x) \text{ 且 } g_i(x) > g_k(x) \forall k \neq i,j \label{eq:m}
    \end{equation}
    \begin{equation}
        g_i(x) = g_j(x) \text{ 且 } g_i(x) < g_k(x) \forall k \neq i,j \label{eq:n}
    \end{equation}
    其中\eqref{eq:m} 为最大$g_i(x)$的类别作为其所属类别，\eqref{eq:n} 为最小$g_i(x)$的类别作为其所属类别。

    在计算机绘图中，我们很难去精确计算$g_i(x) - g_j(x) = 0$，这个方程中的$x_1$,$x_2$的具体映射关系，所以我们会采取令$z(x) = g_i(x) - g_j(x)$。此时我们如果将向量$x$的所属区域细分成网格，并去计算每个网格点的$z(x)$，接下来我们只需要绘制等高线$z(x) = 0$，即可完成分类线。

    实验代码如\href{run:main.py}{main.py}中的主函数部分所示。

    \subsubsection{似然率决策规则}

    分类决策界面如下图:

    \begin{minipage}[t]{0.5\linewidth}
        \centering
        \includegraphics[width=\linewidth]{../question1/X1_data_likelihood_predict_result}
        \label{fig:likelihood1} %此处的label相当于一个图片的专属标志，目的是方便上下文的引用
    \end{minipage}%
    \begin{minipage}[t]{0.5\linewidth}
        \centering
        \includegraphics[width=\linewidth]{../question1/X2_data_likelihood_predict_result}
        \label{fig:likelihood2} %此处的label相当于一个图片的专属标志，目的是方便上下文的引用
    \end{minipage}

    \paragraph{错误率}

    可以看到，X1中的预测数据错误量为68个，错误率为6.8\%,X2中的预测数据错误量为65个，错误率为6.5\%。

    实验结论:
    \begin{enumerate}
        \item 似然率决策规则的分类界面为线性
        \item 似然率决策规则对于先验概率较为敏感，其分界线会随着数据集先验概率变化而变化
        \item 在已知数据概率分布函数的情况下，似然率决策规则的分类效果较好
    \end{enumerate}

    \subsubsection{贝叶斯风险决策规则}

    分类决策界面如下图:

    \begin{minipage}[t]{0.5\linewidth}
        \centering
        \includegraphics[width=\linewidth]{../question1/X1_data_bayes_predict_result}
        \label{fig:bayes1} %此处的label相当于一个图片的专属标志，目的是方便上下文的引用
    \end{minipage}%
    \begin{minipage}[t]{0.5\linewidth}
        \centering
        \includegraphics[width=\linewidth]{../question1/X2_data_bayes_predict_result}
        \label{fig:bayes2} %此处的label相当于一个图片的专属标志，目的是方便上下文的引用
    \end{minipage}

    \paragraph{错误率}  可以看到，X1中的预测数据错误量为75个，错误率为7.5\%,X2中的预测数据错误量为77个，错误率为7.7\%。

    实验结论:
    \begin{enumerate}
        \item 贝叶斯风险决策规则的分类界面近似为线性 (可能由实验误差或给定$C_{ij}$不同引起)
        \item 对比于似然率决策规则，贝叶斯风险决策规则错误率可能会高
    \end{enumerate}

    \subsubsection{最小欧几里得距离分类器}

    分类决策界面如下图:

    \begin{minipage}[t]{0.5\linewidth}
        \centering
        \includegraphics[width=\linewidth]{../question1/X1_data_Euclid_predict_result}
        \label{fig:Euclid1} %此处的label相当于一个图片的专属标志，目的是方便上下文的引用
    \end{minipage}%
    \begin{minipage}[t]{0.5\linewidth}
        \centering
        \includegraphics[width=\linewidth]{../question1/X2_data_Euclid_predict_result}
        \label{fig:Euclid2} %此处的label相当于一个图片的专属标志，目的是方便上下文的引用
    \end{minipage}

    \paragraph{错误率}  可以看到，X1中的预测数据错误量为68个，错误率为6.8\%,X2中的预测数据错误量为78个，错误率为7.8\%。

    实验结论:
    \begin{enumerate}
        \item 最小欧几里得距离分类器为线性
        \item 最小欧几里得距离分类器对先验概率无反应，其分类界面不会随着数据集先验概率变化而变化
        \item 对比X1,X2数据集，最小欧几里得距离分类器的错误率明显会在先验概率不相等的情况下高于相等的情况，即其最佳条件适用于先验概率相等的情况
    \end{enumerate}


    \section{问题二}
    \begin{proof}

        由题意得:

        $\epsilon_1$ 为第一类问题的错误率(即本属于第一类问题但是误判成第二类问题)， $\epsilon_2$ 为第二类问题的错误率(即本属于第二类问题但是误判成第一类问题)。

        这里设第一类问题标签为$\omega_1$，第二类问题标签为$\omega_2$。

        则有:
        \begin{equation}
            \epsilon_1 = \int_{\omega_2} P(x|\omega_1)dx \label{eq:2.1}
        \end{equation}
        \begin{equation}
            \epsilon_2 = \int_{\omega_1} P(x|\omega_2)dx \label{eq:2.2}
        \end{equation}

        令$\epsilon_1 = \epsilon = \text{常数}$，则问题可以转化为求解使$\epsilon_2$最小的判决域。

        使用拉格朗日乘子法，得到:
        \begin{equation}
            y = \epsilon_2 + \theta(\epsilon_1 - \epsilon) \label{eq:2.3}
        \end{equation}

        将~\eqref{eq:2.1}和~\eqref{eq:2.2}代入~\eqref{eq:2.3}，得到:
        \begin{equation}
            y = \epsilon_2 + \theta(\int_{\omega_2} P(x|\omega_1)dx - \epsilon) \label{eq:2.4}
        \end{equation}

        又错误率$\epsilon_2 = 1 - P_2(correct) = 1 - \int_{\omega_2} P(x|\omega_2)dx$，代入~\eqref{eq:2.4}，可得
        \begin{equation}
            y = 1 - \int_{\omega_2} P(x|\omega_2)dx + \theta(\int_{\omega_2} P(x|\omega_1)dx - \epsilon) \newline
            = (1 - \theta \epsilon) - \int_{\omega_2} \left[ P(x|\omega_2) - \theta P(x|\omega_1) \right]\label{eq:2.5}
        \end{equation}

        一般来说，我们无法用解析方法直接求出符合条件的$\omega_2$的判决域$S_2$，但可以注意到$\theta$在式子中其实是确定的，且$P(x|\omega_2)$、$P(x|\omega_1)$在给定空间中也是确定的，此时只需选择的满足条件$P(x|\omega_2) - \theta P(x|\omega_1) > 0$的全体$x$作为$\omega_2^{*}$即可保证此时所求的y值比其他方法取得的y值要小。

        因为这种取法下，$\omega_2^{*}$是使被积函数取正数时最大的域，即此时应该取$\omega_2$，。

        于是在两类分类问题中，可以约束某个类别的错误率不变，即$\epsilon_1 = \epsilon$，此时最小化另一类别错误率得到的似然率测试规则为:
        \begin{align}
            \text{decide } x \in \omega_2 \text{ if } & P(x|\omega_2) - \theta P(x|\omega_1) > 0 \\
            & \frac{P(x|\omega_2)}{P(x|\omega_1)} > \theta
        \end{align}

        同理可得:
        \begin{align}
            \text{decide } x \in \omega_1 \text{ if } & P(x|\omega_2) - \theta P(x|\omega_1) < 0 \\
            & \frac{P(x|\omega_1)}{P(x|\omega_2)} > \theta \label{al:2.6}
        \end{align}

        又$P(x|\omega_2) = \frac{P(\omega_2|x) P(x)}{P(\omega_2)}$，$P(x|\omega_1) = \frac{P(\omega_1|x) P(x)}{P(\omega_1)}$，代入~\eqref{al:2.6}有:
        \begin{align}
            \text{decide } x \in \omega_1 \text{ if } & \frac{\frac{P(\omega_1|x) P(x)}{P(\omega_1)}}{\frac{P(\omega_2|x) P(x)}{P(\omega_2)}} > \theta \\
            \frac{P(\omega_1|x)}{P(\omega_2|x)} > \theta \frac{P(\omega_1)}{P(\omega_2)} \label{al:2.7}
        \end{align}

        又$P(\omega_1)$、$P(\omega_2)$、$\theta$均为常数，因此可将其简写为$\theta$，即:
        \[
        \text{decide } x \in \omega_1 \text{ if } \frac{P(\omega_1|x)}{P(\omega_2|x)} > \theta
        \]

        证毕。

    \end{proof}
\end{document}